package hanjia;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Description:
 * Author:    Dane
 * CreateTime:2025/2/14-下午1:39
 * Since  :   1.0
 * Version:   1.0
 */
public class LeetCode40 {
   int pre=0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        int start=0;
        List<Integer> result=new ArrayList<>();
        List<List<Integer>> results=new ArrayList<>();
        Arrays.sort(candidates);
        backtracking(start,candidates,target,result,results);
        return results;

    }

    private void backtracking(int start, int[] candidates, int target, List<Integer> result, List<List<Integer>> results) {


        if (sum(result)>target){
            return;
        }
        if (sum(result)==target){
            pre=result.get(0);
            results.add(new ArrayList<>(result));
        }


        for (int i=start;i<candidates.length;i++){
            if (candidates[i]>target){
                return;
            }
            if (candidates[i]==pre){
                continue;
            }
            result.add(candidates[i]);
            backtracking(i+1,candidates,target,result,results);
            pre=candidates[i];
            result.remove(result.size()-1);




        }
    }

    private int sum(List<Integer> result){
        int sum=0;
        for (int i:result){
            sum+=i;
        }
        return sum;
    }
}
